package com.shuang.graph16;

//import java.util.Arrays;
//import java.util.Scanner;
//
//public class Main {
//    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//        int n = scanner.nextInt();
//        int m = scanner.nextInt();
//
//        int[][] grid = new int[n + 1][n + 1];
//        for (int i = 0; i <= n; i++) {
//            Arrays.fill(grid[i], Integer.MAX_VALUE);
//        }
//
//        for (int i = 0; i < m; i++) {
//            int p1 = scanner.nextInt();
//            int p2 = scanner.nextInt();
//            int val = scanner.nextInt();
//            grid[p1][p2] = val;
//        }
//
//        int start = 1;
//        int end = n;
//
//        // 存储每个节点到源点的最短距离
//        int[] minDist = new int[n + 1];
//        Arrays.fill(minDist, Integer.MAX_VALUE);
//
//        // 记录顶点是否被访问过
//        boolean[] visited = new boolean[n + 1];
//
//        minDist[start] = 0;  // 起始点到自身的距离为0
//
//        for (int i = 1; i <= n; i++) { // 遍历所有节点
//
//            int minVal = Integer.MAX_VALUE;
//            int cur = 1;
//
//            // 1、选距离源点最近且未访问过的节点
//            for (int v = 1; v <= n; ++v) {
//                if (!visited[v] && minDist[v] < minVal) {
//                    minVal = minDist[v];
//                    cur = v;
//                }
//            }
//
//            visited[cur] = true;  // 2、标记该节点已被访问
//
//            // 3、第三步，更新非访问节点到源点的距离（即更新minDist数组）
//            for (int v = 1; v <= n; v++) {
//                if (!visited[v] && grid[cur][v] != Integer.MAX_VALUE && minDist[cur] + grid[cur][v] < minDist[v]) {
//                    minDist[v] = minDist[cur] + grid[cur][v];
//                }
//            }
//        }
//
//        if (minDist[end] == Integer.MAX_VALUE) {
//            System.out.println(-1); // 不能到达终点
//        } else {
//            System.out.println(minDist[end]); // 到达终点最短路径
//        }
//    }
//}

//堆优化版
import java.util.*;

//自定义邻接表存储的链表类型
class Edge {
    int to; // 邻接节点（用于存储上个节点所指向的该节点的值）
    int val; // 边的权重 上个节点指向该节点的权值

    Edge(int to, int val) {
        this.to = to;
        this.val = val;
    }
}

//自定义优先级队列中的排序方式 根据节点距离源点的最小距离从小到大排序
class MyComparison implements Comparator<Pair<Integer, Integer>> {
    @Override
    public int compare(Pair<Integer, Integer> lhs, Pair<Integer, Integer> rhs) {
        return Integer.compare(lhs.second, rhs.second);
    }
}

//定义优先级队列中存的类型 节点的值 和 该节点距离源点的最小距离
class Pair<U, V> {
    U first;
    V second;

    public Pair(U first, V second) {
        this.first = first;
        this.second = second;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();

        //邻接表存储 用于找边
        List<List<Edge>> grid = new ArrayList<>(n + 1);
        for (int i = 0; i <= n; i++) {
            grid.add(new ArrayList<>());
        }

        for (int i = 0; i < m; i++) {
            int p1 = scanner.nextInt();
            int p2 = scanner.nextInt();
            int val = scanner.nextInt();
            grid.get(p1).add(new Edge(p2, val));
        }

        int start = 1; // 起点
        int end = n; // 终点

        // 存储每个节点到源点的最短距离
        int[] minDist = new int[n + 1];
        Arrays.fill(minDist, Integer.MAX_VALUE);

        // 记录顶点是否被访问过
        boolean[] visited = new boolean[n + 1];

        // 优先队列中存放 Pair<节点，该节点到源点的最小距离>
        PriorityQueue<Pair<Integer, Integer>> pq = new PriorityQueue<>(new MyComparison());

        // 初始化队列，源点到源点的距离为0，所以初始为0
        pq.add(new Pair<>(start, 0));

        minDist[start] = 0; // 起始点到自身的距离为0

        while (!pq.isEmpty()) {
            // 1. 第一步，选源点到哪个节点近且该节点未被访问过（通过优先级队列来实现）
            // <节点， 源点到该节点的距离> 每次取出的都是排好序的 距离源点最短距离的pair类型
            Pair<Integer, Integer> cur = pq.poll();

            if (visited[cur.first]) continue;

            // 2. 第二步，未被访问过的节点进行标记标记
            visited[cur.first] = true;

            // 3. 第三步，更新非访问节点到源点的距离（即更新minDist数组）
            for (Edge edge : grid.get(cur.first)) { // 遍历 cur指向的节点，cur指向的节点为 edge
                // cur指向的节点edge.to，这条边的权值为 edge.val
                if (!visited[edge.to]
                        && minDist[cur.first] + edge.val < minDist[edge.to]) { // 更新minDist
                    minDist[edge.to] = minDist[cur.first] + edge.val;
                    pq.add(new Pair<>(edge.to, minDist[edge.to]));
                }
            }
        }

        if (minDist[end] == Integer.MAX_VALUE) {
            System.out.println(-1); // 不能到达终点
        } else {
            System.out.println(minDist[end]); // 到达终点最短路径
        }
    }
}
